package com.gitee.feizns.explore.data_structure.graph;

/**
 * 997. 找到小镇的法官
 * @author feizns
 * @since 2020/2/26
 */
public class FindJudge {

    public static int findJudge22(int N, int[][] trust) {
        int[][] trustMark = new int[N + 1][2];
        for(int[] t : trust) {
            trustMark[t[0]][0]++;
            trustMark[t[1]][1]++;
        }
        for (int i = 1; i <= N; i++) {
            if ( trustMark[i][0] == 0 && trustMark[i][1] == N - 1 ) {
                return i;
            }
        }
        return -1;
    }

    public static int findJudge(int N, int[][] trust) {
        int[][] trustMark = create(N);
        for(int[] t : trust) {
            trustMark[t[0]][t[1]] = 1;
            trustMark[0][t[0]]++;
            trustMark[t[1]][0]++;
        }
        for (int i = 1; i <= N; i++) {
            if ( trustMark[0][i] == 0 && trustMark[i][0] == N - 1 ) {
                return i;
            }
        }
        return -1;
    }

    private static int[][] create(int N) {
        int[][] ret = new int[N + 1][N + 1];
        for(int i = 1; i < N + 1; i++)
            ret[i] = new int[N + 1];
        return ret;
    }

    public static void main(String[] args) {
        final int judge = findJudge22(2, new int[][]{new int[]{1, 2}});
        System.out.println(judge);
    }

}
